package com.mesnac.sort;

public class MinHeapSort {

	public void minHeapInsert(int a[], int i, int num){
		a[i] = num;
		minHeapFixup(a,i);
	}
	private void minHeapFixup(int a[],int i){
		int j = (i-1)/2;
		int temp = a[i];
		while(j >= 0 && i!=0){
			if(a[j] <= temp)
				break;
			a[i] = a[j];
			i = j;
			j = (i -1) /2;		
		}
		a[j] = temp;
	}
	/**
	 * 
	 * @param n 节点总数
	 * @param a
	 */
	public void minHeapDel(int n,int a[]){
		swap(0,n-1,a);
		minHeapFixdown(a,0,n-1);
	}
	private void swap(int i ,int j, int a[]){
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
	
	private void minHeapFixdown(int a[],int i, int n){
		int temp = a[i];
		int j = i*2+1;
		while(j < n){
			if(j + 1 < n && a[j+1] < a[j])//左右节点最小的
				j++;
			if(a[j] >= temp)
				break;
			a[i] = a[j];
			i = j;
			j = 2 * i + 1;
			
		}
		a[i] = temp;
	}
	
	//堆化数组
	public void minHeapCreate(int a[],int n){
		for(int i = n/2 - 1; i >= 0; i--){
			minHeapFixdown(a,i,n);
		}
	}
	// 最小堆的逆序排序
	public void minHeapSortDesc(int a[], int n){
		for(int i = n-1; i >= 1; i--){
			swap(0,i,a);
			minHeapFixdown(a,0,i);
		}
	}
	
	public static void main(String args[]){
		int a[] = {3,1,2,7,4,9,8,6,5,10};
		MinHeapSort s = new MinHeapSort();
		s.minHeapCreate(a, 10);
		s.minHeapSortDesc(a,10);
		for(int i = 0; i < 10; i++){
			System.out.println(a[i]);
		}
	}
}
